Communication entails the transfer of information from one point to another. A communication may be transmitted in many forms (e.g., voice, data, video, facsimile). Communication of digital data is usually done by code. A code is a set of characters (e.g., Morse code, American Standard Code for Information Interchange (ASCII)). Typically, each character in a code consists of binary bits.
Noise is any unwanted signal that might interfere with the intended communication. Examples of noise include a waveform that covers the frequency band of the particular communication channel over which the communication is transmitted, a voltage impulse signal (i.e., a voltage spike), interference (i.e., crosstalk) from one communication channel to another, a single frequency tone, interference with the communication by itself (i.e., an echo). Noise may result in the modification of one or more of the binary bits that make up the communication.
Prior to transmitting a signal, a modulator-demodulator (modem) converts a digital signal to an analog signal. Upon receiving an analog signal, a modem converts the analog signal to a digital signal. Some modems format the data in a digital signal in one way or another prior to converting the digital signal to an analog signal for subsequent transmission. For example, the data may be framed, or packetized, so that a cyclic redundancy check can be used by the recipient of the transmission to determine if the signal received is the same as the signal sent. Such a check helps the recipient determine if an error occurred in the data. Also, a facsimile transmission may be formatted so that 1) only a certain number of picture elements occur per scan line, 2) only valid compression codes are used, 3) an end-of-line code occurs at the end of each scan line, and 4) a high correlation of black picture elements exist from scan line to scan line. Furthermore, the binary bits may be restricted to a certain set of values (e.g., ASCII characters restricted to a range of binary values that is less than the maximum range of 0 to 255). These are only a few examples of how a modem transmission may be formatted. The present invention can be applied to other formatting methods and is, therefore, not limited by the particular formatting method employed.
Typically, communications transmitted using quadrature amplitude modulated (QAM) modems are transmitted as a series of symbols. Each symbol may consist of several binary bits. The symbols can be visualized as points on a two-dimensional x-y plot (i.e., a constellation). Each point has a fixed bit assignment. The assignments are usually chosen so that adjacent symbols differ in only one bit position. For example, the zero degree point, the 90 degree point, the 180 degree point, and the 270 degree point on a unit circle may be represented by the following symbols: 00, 01, 11, 10 respectively. Note that the zero degree point and the 270 degree point also differ in only one bit position. Typically, symbols are chosen to maximize the distance between adjacent symbols. These two steps reduce the likelihood that one symbol will be mistaken for another. Exactly how this reduced likelihood is achieved is discussed below.
When a symbol is received, its position in the constellation is measured, and it is assigned the bit sequence of the closest point in the constellation. By maximizing the distance between adjacent constellation points, an error in a symbol may result in a measurement that is sufficiently close to the intended constellation point that the error does not prevent the symbol from being assigned the correct bit sequence. But an error in a symbol may result in a measurement that is so far away from the intended constellation point that the intended symbol will be mistaken for an unintended constellation point and assigned an incorrect bit sequence (i.e., the bit sequence for the unintended constellation point).
Some modems use differential phase coding which indicates whether or not there has been a change of phase between adjacent symbols. If the phase of one symbol is mistaken, a mistake will be made in the next symbol.
Typically, a communication is not transmitted "as is" because it may contain long strings of binary ones or zeros. These long strings will make it difficult to accurately count the ones or zeros, and these long strings may be mistaken for a control signal (e.g., start signal, stop signal, etc.). Also, a repetitive pattern within a communication may produce a strong frequency component that may interfere with the communication. For these reasons, a communication is scrambled prior to transmission and descrambled upon reception.
Typically, a scrambler is a pseudo-random linear sequence generator consisting of a shift-register having a number of outputs (i.e., taps) connected to an exclusive-or gate. The output of the exclusive-or gate is logically fed back into the input of the shift-register to create the pseudo-random linear sequence. A communication is scrambled by logically combining the output of the exclusive-or gate with the binary bits of the communication. Each uniquely configured pseudo-random linear sequence generator can be described, mathematically, by a polynomial (e.g., 1+x**-6+x**-7).
Descrambling is achieved by creating a mirror image of the scrambling process. Since the descrambler contains a shift-register, an erroneous bit lingers in the shift-register until it is shifted out. Therefore, an erroneously descrambled bit will cause additional errors until the erroneous bit is shifted out of the shift-register. Note that each of the subsequently produced error-bits also linger for the same duration.
As noted above, noise may introduce bit-errors in the communication. Typically, these errors are corrected by toggling the received bits until a determination is made that the error has been corrected. This exhaustive-search-type method of correcting errors can be extremely time-consuming. Also, such a method would be unsuccessful if the time required to correct an error exceeds the mean time between failure of the error-correction device.
The present invention discloses a device for and method of correcting bit errors in a formatted modem transmission that does not employ an exhaustive-search scheme. It is believed that the present invention corrects errors faster than could be done using an exhaustive-search scheme. Also, the increased performance obtained by the present invention may result in the correction of errors that cannot be corrected using an exhaustive-search scheme.
U.S. Pat. No. 4,760,576, entitled "ERROR CORRECTION METHOD," discloses a method of correcting errors that occur in data that is arranged in rows and columns. The errors are corrected by adding an error correction code to the previously known codes for correcting row errors and column errors. The present invention does not rely on any of these codes to correct errors. The present invention corrects errors by generating error patterns and correction patterns based on a method of reducing the error-search tree.
U.S. Pat. No. 5,010,554, entitled "ERROR CORRECTION METHOD AND APPARATUS," discloses a device for and method of correcting errors that is faster than devices and methods that use an overall parity bit. U.S. Pat. No. 5,010,554 divides the data to be corrected into a significant part and an insignificant part. A parity bit is provided for the significant part. Doing a parity check on the significant part reduces the number of computations needed to correct the errors in the data. The present invention does not rely on parity bits to correct errors. The present invention looks at the receiving modem as being the source of any error. Therefore, the present invention characterizes the receiving modem so that error patterns can be identified and corrected quickly.